package leetcode11;

public class test61 {
    /**
     * 在排序数组中查找元素的第一个和最后一个位置
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int leftBoder = getLeftBoder(nums, target);
        int rightBoder = getRightBoder(nums, target);
        if (rightBoder - leftBoder > 1) {
            return new int[] { leftBoder + 1, rightBoder - 1 };
        }
        return new int[] { -1, -1 };
    }

    public int getLeftBoder(int[] nums, int target) {
        int n = nums.length;
        int leftBoder = -2; // 不包括target

        int l = 0;
        int r = n - 1;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) { // 找到一个target更新左边界继续找
                r = mid - 1;
                leftBoder = r;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return leftBoder;
    }

    public int getRightBoder(int[] nums, int target) {
        int n = nums.length;
        int rightBoder = -2; // 不包括target

        int l = 0;
        int r = n - 1;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) { // 找到一个target更新右边界继续找
                l = mid + 1;
                rightBoder = l;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return rightBoder;
    }
}
